package com.example.dynamicplanning;

import java.util.Arrays;

/**
 * 913. 猫和老鼠 hard
 * 两位玩家分别扮演猫和老鼠，在一张 无向 图上进行游戏，两人轮流行动。
 *
 * 图的形式是：graph[a] 是一个列表，由满足 ab 是图中的一条边的所有节点 b 组成。
 *
 * 老鼠从节点 1 开始，第一个出发；猫从节点 2 开始，第二个出发。在节点 0 处有一个洞。
 *
 * 在每个玩家的行动中，他们 必须 沿着图中与所在当前位置连通的一条边移动。例如，如果老鼠在节点 1 ，那么它必须移动到 graph[1] 中的任一节点。
 *
 * 此外，猫无法移动到洞中（节点 0）。
 *
 * 然后，游戏在出现以下三种情形之一时结束：
 *
 * 如果猫和老鼠出现在同一个节点，猫获胜。
 * 如果老鼠到达洞中，老鼠获胜。
 * 如果某一位置重复出现（即，玩家的位置和移动顺序都与上一次行动相同），游戏平局。
 * 给你一张图 graph ，并假设两位玩家都都以最佳状态参与游戏：
 *
 * 如果老鼠获胜，则返回 1；
 * 如果猫获胜，则返回 2；
 * 如果平局，则返回 0 。
 *
 * 示例 1：
 *
 * 输入：graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]
 * 输出：0
 * 示例 2：
 *
 *
 * 输入：graph = [[1,3],[0],[3],[0,2]]
 * 输出：1
 */
public class CatMouseGame {
    private static int[][][] step;
    private static int[][] gragh;

    public static int catMouseGame(int[][] graph) {
        int N = graph.length;
        step = new int[N][N][15];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                Arrays.fill(step[i][j], -1);
            }
        }
        gragh = graph;
        return dp(1, 2, 0);
    }

    private static int dp(int mouse, int cat, int level) {
        if (level >= 15) {
            return 0;
        }
        if (step[mouse][cat][level] != -1) {
            return step[mouse][cat][level];
        }
        // 老鼠
        if (level % 2 == 0) {
            int cwin = 1;
            int[] nexts = gragh[mouse];
            for (int next : nexts) {
                if (next == cat) {
                    continue;
                }
                if (next == 0) {
                    return step[mouse][cat][level] = 1;
                }
                int f = dp(next, cat, level + 1);
                if (f == 1) {
                    return step[mouse][cat][level] = 1;
                }
                if (f != 2) {
                    cwin = 0;
                }
            }
            if (cwin == 1) {
                return step[mouse][cat][level] = 2;
            } else {
                return step[mouse][cat][level] = 0;
            }
        } else {
            //猫
            int mwin = 1;
            int[] nexts = gragh[cat];
            for (int next : nexts) {
                if (next == 0) {
                    continue;
                }
                if (next == mouse) {
                    return step[mouse][cat][level] = 2;
                }
                int f = dp(mouse, next, level + 1);
                if (f == 2) {
                    return step[mouse][cat][level] = 2;
                }
                if (f != 1) {
                    mwin = 0;
                }
            }
            if (mwin == 1) {
                return step[mouse][cat][level] = 1;
            } else {
                return step[mouse][cat][level] = 0;
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(catMouseGame(new int[][]{{1, 3}, {0}, {3}, {0, 2}}));

        System.out.println('a'+'1');
    }
}
